# Problem 15
#
# Starting in the top left corner of a 2 x 2 grid, there are 
# 6 routes (without backtracking) to the bottom right corner.
#
# How many routes are there through a 20 x 20 grid?

def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n-1)

def choose(n, k):
    return fact(n) / (fact(k) * fact(n-k))

# You actually accidentally ran into the solution for this problem
# when browsing BetterExplained.
# The trick is to recognize this a problem involving combinations.
print "-> ", choose(40,20) 
